package com.atguigu.binaryTree;

import java.util.LinkedList;
import java.util.Queue;

public class CBT {
    //判断是否是完全二叉树
    public static boolean IsCBT(TreeNode root){
        if(root==null) return true;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        boolean leaf=false;
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            TreeNode l=cur.left; //左子树
            TreeNode r=cur.right; //右子树
            if(l==null && r!=null){
                return false; //左子树空 但右子树却不空
            }
            if(leaf && !(l==null && r==null)){
                return false; //出现缺节点的情况，此时后面应该全为叶子结点
            }
            if(l==null || r==null){
                leaf=true;
            }
            if(l!=null) queue.offer(l);
            if(r!=null) queue.offer(r);
        }
        return true;
    }
}
